剑指Offer 31 连续子数组的最大和

题目描述

输入一个整形数组，数组里有正数也有负数。
数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。
求所有子数组的和的最大值。要求时间复杂度为O(n)。

例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5，和最大的子数组为3, 10, -4, 7, 2，
因此输出为该子数组的和18。

思路

这道题应该做过一遍，所以思路比较清楚，第一种是说直接将数从头加到尾，每一位都变成之前所有数的和；然后你就会发现，有些数是负的啊，一看就知道不应该要他；所以想法就是如果是负数，就变成当前值；
（1，-2，3）–>（1，-1，2）；你-1加3肯定更小啊；所以是这样的
（1，-2，3）–>（1，-1，3）；前边是负值，你就重新计算的啦；

动态规划：
很明显的，如果前面是负的，就重新来，否则继续加；

代码

static public int FindGreatestSumOfSubArray(int[] array) {
      if (array==null&&array.length==0)
          return 0;
       int a=0;
       int max=Integer.MIN_VALUE;
       for ( int i = 0 ; i <array.length;i++)
       {
           if (a<=0)
               a=array[i];
           else
           a+=array[i];
           if ( a>max)
               max = a;
       }
       return  max;
   }
   static  public  int FindGreatestSumOfSubArray1(int [] array)
   {
       if (array.length==0)
           return 0;
       int sum = array[0],tempsum = array[0];
       for (int i =1;i<array.length;i++)
       {
           tempsum = (tempsum<0)?array[i]:array[i]+tempsum;
           sum = (tempsum>sum)? tempsum:sum;
       }
       return sum;
   }

收获

心急吃不了热豆腐啊，做过的题，结果就忘记什么用例了，上来就做；
用了一下动态规划，算法课，数据结构课，真的是可以一直学习的课程啊；

2017-03-30